#include "string_array.h"
#include <cstring>
#include <fstream>
#include <iostream>
using namespace std;

void myStr::print()
{
    for (int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext()
{
    for (int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal()
{
    for (int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

myStr::myStr(const char *str)
{
    length = strlen(str);
    data = new char[length + 1];
    strcpy(data, str);
    next = new int[length + 1];
    nextVal = new int[length + 1];
}
myStr::~myStr()
{
    delete[] data;
    delete[] next;
    delete[] nextVal;
}
myStr::myStr(const myStr &other)
{
    length = other.length;
    data = new char[length + 1];
    strcpy(data, other.data);
    next = new int[length + 1];
    nextVal = new int[length + 1];
    memcpy(next, other.next, (length + 1) * sizeof(int));
    memcpy(nextVal, other.nextVal, (length + 1) * sizeof(int));
}

void myStr::kmp_next()
{
    next[0] = -1;
    next[1] = 0;
    int j = 1;
    int k = 0;
    while (j < length - 1)
    {
        if (data[j] == data[k])
        {
            next[j + 1] = k + 1;
            j++;
            k++;
        }
        else
        {
            k = next[k];
        }
        if (k == -1)
        {
            next[j + 1] = 0;
            j++;
            k = 0;
        }
    }
    for (int i = 0; i < length; i++)
    {
        next[i] += 1;
    }
}
void myStr::kmp_nextVal()
{
    nextVal[0] = -1;
    int j = 0;
    int k = -1;
    while (j < length)
    {
        if (k == -1 || data[k] == data[j])
        {
            j++;
            k++;
            if (data[k] != data[j])
            {
                nextVal[j] = k;
            }
            else
            {
                nextVal[j] = nextVal[k];
            }
        }
        else
        {
            k = nextVal[k];
        }
    }
    for (int i = 0; i < length; i++)
    {
        nextVal[i] += 1;
    }
}
int simpleMatch(const myStr &matchS, const myStr &matchT)
{
    myStr S = matchS;
    myStr T = matchT;
    T.kmp_next();
    int i = 0;
    int j = 0;
    while (i < S.length && j < T.length)
    {
        if (S.data[i] == T.data[j] || j == -1)
        {
            i++;
            j++;
        }
        else
        {
            j = T.next[j] - 1;
        }
    }
    if (j >= T.length)
    {
        return i - T.length + 1;
    }
    else
    {
        return -1;
    }
}
int kmpMatch(const myStr &matchS, const myStr &matchT)
{
    myStr S = matchS;
    myStr T = matchT;
    T.kmp_nextVal();
    int i = 0;
    int j = 0;
    while (i < S.length && j < T.length)
    {
        if (S.data[i] == T.data[j] || j == -1)
        {
            i++;
            j++;
        }
        else
        {
            j = T.nextVal[j] - 1;
        }
    }
    if (j >= T.length)
    {
        return i - T.length + 1;
    }
    else
    {
        return -1;
    }
}

// 字符串替换
// 串的替换，要求在主串S中，从位置start开始查找是否存在子串T
// 若主串S中存在子串T，则用子串V替换子串R，且函数返回1；若主串中不存在子串T，则函数返回0，start取值从1开始
bool replaceStr(myStr &S, const int &start, const myStr &T, const myStr &V)
{
    int n = S.length;
    int m = T.length;
    int i = start;
    if (i < 1 || i > n || m <= 0 || m > n - i + 1)
    {
        return false;
    }
    int count = 0;
    while (i <= n - m + 1 && count < m)
    {
        count = 0;
        for (int j = 0; j < m; j++)
        {
            if (S.data[i - 1 + j] == T.data[j])
            {
                count++;
            }
        }
        i++;
    }
    if (count >= m)
    {
        int pos = i - 1;
        int h = V.length;
        char *newdata = new char[n - m + h + 1];
        for (int j = n; j >= pos - 1 + m; j--)
        {
            newdata[j + h - m] = S.data[j];
        }
        for (int j = 0; j < h; j++)
        {
            newdata[pos - 1 + j] = V.data[j];
        }
        for (int j = 0; j < pos - 1; j++)
        {
            newdata[j] = S.data[j];
        }

        delete[] S.data;
        S.data = newdata;
        S.length = n - m + h;
        return true;
    }
    else
    {
        return false;
    }
}

// 稀疏矩阵类，使用三元组存储稀疏矩阵元素，实现以下功能
myMatrix::myMatrix(const int &rNum, const int &cNum, const int &nNum, const int *data) : rowNum(rNum), colNum(cNum), nodeNum(nNum)
{
    nodeList = new matrixNode[nodeNum];
    int m = 0;
    for (int i = 0; i < rowNum; i++)
    {
        for (int a = 0; a < colNum; a++)
        {
            for (int j = 0; j < nodeNum; j++)
            {
                if (data[j * 3] == i && data[j * 3 + 1] == a)
                {
                    nodeList[m].row = data[j * 3];
                    nodeList[m].col = data[j * 3 + 1];
                    nodeList[m].value = data[j * 3 + 2];
                    m++;
                }
            }
        }
    }
}

myMatrix::~myMatrix()
{
    delete[] nodeList;
}

void myMatrix::printMatrix()
{
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for (int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}

myMatrix::myMatrix() : rowNum(0), colNum(0), nodeNum(0)
{
    nodeList = nullptr;
}

// 实现快速转置算法，转置结果存在T中
void myMatrix::FastTransposeSMatrix(myMatrix &T)
{
    T.colNum = rowNum;
    T.nodeNum = nodeNum;
    T.rowNum = colNum;
    T.nodeList = new matrixNode[T.nodeNum];
    int q = 0; // 新三元组的下标
    int p = 0; // 旧三元组的下标
    int *num = new int[colNum];
    int *cpot = new int[colNum];
    if (T.nodeNum)
    {
        // num数组元素置0
        for (int i = 0; i < colNum; i++)
        {
            num[i] = 0;
        }
        // 遍历旧三元组M每一列的非零元个数
        for (int t = 0; t < nodeNum; t++)
        {
            num[nodeList[t].col]++;
        }
        cpot[0] = 0;
        int col;
        // 求第col列中第一个非零元在T中的序号
        for (col = 1; col < colNum; col++)
        {
            cpot[col] = cpot[col - 1] + num[col - 1];
        }
        for (p = 0; p < nodeNum; p++)
        {
            col = nodeList[p].col;
            q = cpot[col];
            T.nodeList[q].row = nodeList[p].col;
            T.nodeList[q].col = nodeList[p].row;
            T.nodeList[q].value = nodeList[p].value;
            cpot[col]++;
        }
    }
}